The Viterbi algorithm has found wide application in the digital communications field, having been used in applications as diverse as satellite communications, hard disk drives, cell phones, wireless personal area networks, and optical fiber channels. In addition to being used for channel equalization, it is an important component for many error-correction coding schemes in the convolutional coding family including trellis codes and turbo codes. Such codes are employed, for example, in the so-called second and third generation (2G/3G) communication standards IS-95, CDMA2000, WCDMA and TD-SCDMA.
Though popular, the Viterbi algorithm in its purest form suffers from various shortcomings. Over the years, many variations of the Viterbi algorithm have been developed to address these deficiencies. Among the variations that have been developed are parallel “sliding block” Viterbi algorithms. (See, e.g., Peter J. Black, Teresa H. Y. Meng, “A 1-Gb/s, Four-State, Sliding Block Viterbi Decoder”, IEEE J Solid-State Cir., vol. 32, no. 6, June 1997.) Designed to address the inherently sequential nature of the original Viterbi algorithm, the parallel Viterbi algorithms are applied to “blocks” of the incoming data stream, augmented by pre- and post-data segments to minimize the effects of the block edges. These additional segments reduce the efficiency of the parallel Viterbi algorithm relative to the original algorithm, but this has widely been considered as the necessary price to pay to achieve parallelization.
As new standards are developed, data rates continue to increase. For example, the IEEE long-reach multi-mode fiber standard IEEE 802.3aq (sometimes referred to as 10 GBASE-LRM) provides for a channel bit rate greater than 10 Gbit/s. With currently available semiconductor technologies, a sequential Viterbi decoder is simply not feasible for such bit rates. Existing sliding block parallel Viterbi decoders either consume an undesirable amount of chip area or require unduly elevated clock rates. These shortcomings are at least partly addressed by the systems and methods disclosed herein.
While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the disclosure to the illustrated embodiments. To the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the scope of the appended claims.